package 单周赛.history;

import java.util.Arrays;

/**
 *
 */
public class 第332场单周赛 {

    public static void main(String[] args) {

        System.out.println(findTheArrayConcVal(new int[]{5, 14, 13, 8, 12}));

        //输入：
        //[5,7,5,7,5]
        //12
        //12
        //输出：
        //5
        //预期：
        //6
        System.out.println(countFairPairs(new int[]{5, 7, 5, 7, 5}, 12, 12));

        int[] nums = {3, 4, 2, 3};
        Arrays.sort(nums, 0, 3);
        System.out.println(Arrays.toString(nums));

    }

    public static long findTheArrayConcVal(int[] nums) {
        long ans = 0;

        int left = 0, right = nums.length - 1;
        while (left < right) {
            long curNum = Long.valueOf("" + nums[left] + nums[right]);
            ans += curNum;
            left++;
            right--;
        }

        if (left == right) {
            ans += nums[left];
        }
        return ans;
    }

    // 排序不会影响答案，先排序，后二分查找
    public static long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long cnt = 0;

        for (int i = 1; i < nums.length; i++) {
            int left = findLeft(nums, 0, i - 1, lower - nums[i]);
            if (left != -1) {
                int right = findRight(nums, 0, i - 1, upper - nums[i]);
                if (right >= left) {
                    cnt += right - left + 1;
                }
            }
        }

        return cnt;
    }

    private static int findRight(int[] temp, int min, int max, int target) {
        int ans = -1;
        int left = min, right = max;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (temp[mid] <= target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    private static int findLeft(int[] temp, int min, int max, int target) {
        int ans = -1;
        int left = min, right = max;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (temp[mid] >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
